\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
%整个文档的布局
\geometry{margin=1.5cm}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
%数学排版
\usepackage{enumerate}
%item加括号
\usepackage{graphicx}
%插图片用的
\usepackage{multicol}
%正文分栏
\usepackage{fancyhdr}
%页眉页脚
\usepackage{layout}
%在文档中改变布局
\usepackage{ctex}
%\usepackage{CJKutf8}   
%用来输入中文的宏包
\usepackage{multirow}
%输入矩阵和行列式


% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}


%\AtBeginDocument{\begin{CJK}{UTF8}{gbsn}}
%	\AtEndDocument{\end{CJK}}
\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{Chenyue (22035026)}
\chead{exe9}
\rhead{2021}


\section*{Exe9.8:}
由题可知：
\[
\begin{aligned}
&\because Au=f,Ae=r \therefore \vert \vert A \vert \vert_{2} \vert \vert u \vert \vert_{2} \geq \vert \vert f \vert \vert_{2}, \vert \vert e \vert \vert_{2} \leq \vert \vert A^{-1} \vert \vert_{2} \vert \vert r \vert \vert_{2}. \\
&\therefore  \dfrac{\vert \vert e \vert \vert_{2}}{\vert \vert u \vert \vert_{2}} \leq \dfrac{\vert \vert A^{-1} \vert \vert_{2} \vert \vert r \vert \vert_{2}}{\dfrac{\vert \vert f \vert \vert_{2}}{\vert \vert A \vert \vert_{2}}} \leq cond(A)\dfrac{\vert \vert r \vert \vert_{2}}{\vert \vert f \vert \vert_{2}} \\
&\because \vert \vert e \vert \vert_{2} \geq \dfrac{\vert \vert r \vert \vert_{2}}{\vert \vert A \vert \vert_{2}},\vert \vert u \vert \vert_{2} \leq \vert \vert A^{-1} \vert \vert_{2} \vert \vert f \vert \vert_{2} \\
&\therefore \dfrac{\vert \vert e \vert \vert_{2}}{\vert \vert u \vert \vert_{2}} \geq \dfrac{\vert \vert r \vert \vert_{2}}{cond(A)\vert \vert f \vert \vert_{2}} 
\end{aligned}
\]
所以定理9.6得证。

\section*{Exe9.9:}
首先由条件数的定义知：$cond(A)=\vert \vert A \vert \vert_{2} \vert \vert A^{-1} \vert \vert_{2}$
\[
\begin{aligned}
&\because\vert \vert A \vert \vert_{2}=\sqrt{\rho(AA^{T})}=\rho(A)=max \vert \lambda(A) \vert,\vert \vert A^{-1} \vert \vert_{2}=max \vert \lambda(A^{-1}) \vert=max\vert \dfrac{1}{\lambda(A)} \vert\\
if \quad n=8&\therefore \vert \vert A \vert \vert_{2}=4 \cdot 8^{2} sin^{2}(\dfrac{7\pi}{16}),\vert \vert A^{-1} \vert \vert_{2}=(4 \cdot 8^{2} sin^{2}(\dfrac{\pi}{16}))^{-1}\\
&\therefore cond(A)=\dfrac{sin^{2}(\dfrac{7\pi}{16})}{sin^{2}(\dfrac{\pi}{16})}=cot^{2}(\dfrac{\pi}{16})\\
if \quad n=1024&\therefore \vert \vert A \vert \vert_{2}=4 \cdot 1024^{2} sin^{2}(\dfrac{1023\pi}{2048}),\vert \vert A^{-1} \vert \vert_{2}=(4 \cdot 1024^{2} sin^{2}(\dfrac{\pi}{2048}))^{-1}\\
&\therefore cond(A)=\dfrac{sin^{2}(\dfrac{1023\pi}{2048})}{sin^{2}(\dfrac{\pi}{2048})}=cot^{2}(\dfrac{\pi}{2048})
\end{aligned}
\]

\section*{Exe9.12:}
如果不要求边界点的值为0，那么如图所示即可达到$K_{rep}=n$。\\
\begin{figure}[htb] 
	
	
	\center{\includegraphics[width=13cm]  {na_exe9_12.png}} 
	
	
	\caption{\label{1} Not require to be 0 at the domain boundary.} 
	
	
\end{figure}

如果要求边界点的值为0，假设$K_{rep}=n$，那么fourier mode为$u=sin(j\pi)$，即在节点处的值都为0，那么它对应的连续函数应该就是$u=0$,所以，矛盾。也就是说$K_{rep}$达不到n。

\section*{Exe9.15:}
不加负号和加负号的情形：
\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_15_1.png}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth} 
		\hspace{2mm}
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_15_2.png}
	\end{minipage}
\end{figure}
\section*{Exe9.19:}
首先我们知道$\rho(T)<1  \Leftrightarrow \lim_{n \to +\infty} T^{n}=0$，接着我们进行定理的证明：\\
\[
\begin{aligned}
Sufficiency &\because \rho(T)<1 \therefore \lim_{n \to +\infty} T^{n}=0\\
&\therefore \lim_{l \to +\infty} e^{(l)}=\lim_{l \to +\infty} T^{l} e^{(0)}=0.\\
Necessity &\because \lim_{l \to +\infty} e^{(l)}=0 \therefore \lim_{l \to +\infty} T^{l} e^{(0)}=0.\\
&\because e^{(0)}\quad is \quad arbitrary \therefore \lim_{n \to +\infty} T^{n}=0 \quad and \quad \rho(T)<1
\end{aligned}
\]
得证。


\section*{Exe9.24:}
\[
\begin{aligned}
&\because u^{*}=-D^{-1}(L+U)u^{(l)}+D^{-1}f,u^{(l+1)}=(1-w)u^{(l)}-wD^{-1}(L+U)u^{(l)}+D^{-1}f\\
&\therefore T_{w}=(1-w)I-wD^{-1}(L+U)=I-\dfrac{wh^{2}}{2}A\\
&T_{w}\vec{w_{k}}=(I-\dfrac{wh^{2}}{2}A)\vec{w_{k}}=(1-\dfrac{wh^{2}}{2}\dfrac{4}{h^{2}}sin^{2}(\dfrac{k\pi}{2n}))\vec{w_{k}}=(1-2wsin^{2}(\dfrac{k\pi}{2n}))\vec{w_{k}}
\end{aligned}
\]
得证。

\section*{Exe9.25:}

\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_25_1.png}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth} 
		\hspace{2mm}
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_25_2.png}
	\end{minipage}
\end{figure}
所以$T_{w}$的谱半径大于等于0.9986，因此收敛的很慢。

\section*{Exe9.28:}
如图所示：
\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_28_1.png}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth} 
		\hspace{2mm}
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_28_2.png}
	\end{minipage}
\end{figure}

\section*{Exe9.41:}
我们知道一个V-cycle的时间花销小于$\dfrac{2WU}{1-2^{-D}}$,而FMG cycle实际上就是多次V-cycle的迭代。所以，我们有一个FMG cycle的时间花销小于$\dfrac{2WU}{1-2^{-D}}(1+2^{-D}+...+2^{-mD})<\dfrac{2WU}{(1-2^{-D})^2}$。\\
当D=1时：
\[
\begin{aligned}
	T_{V-cycle}&=2WU(1+2^{-1}+...+2^{-m})=2WU(2-\dfrac{1}{2^{m}})\\
	T_{FMG-cycle}&=2WU(2-\dfrac{1}{2^{m}})^2
\end{aligned}
\]
当D=2时：
\[
\begin{aligned}
	T_{V-cycle}&=2WU(1+2^{-2}+...+2^{-2m})=2WU(\dfrac{4}{3}-\dfrac{1}{3\cdot 4^{m}})\\
	T_{FMG-cycle}&=2WU(\dfrac{4}{3}-\dfrac{1}{3\cdot 4^{m}})^2
\end{aligned}
\]
当D=3时：
\[
\begin{aligned}
	T_{V-cycle}&=2WU(1+2^{-3}+...+2^{-3m})=2WU(\dfrac{8}{7}-\dfrac{1}{7\cdot8^{m}})\\
	T_{FMG-cycle}&=2WU(\dfrac{8}{7}-\dfrac{1}{7\cdot8^{m}})^2
\end{aligned}
\]
\section*{Exe9.47:}
在精细网格上relax使得高频模式被削减的很快，然后进行restrict到粗网格上使得一部分精细网格上的低频模式变为粗网格中的高频模式，在粗网格上进行求解残差方程，并将它interpolate回细网格，这样就削减了低频模式，最后再次在精细网格上relax使得高频模式被削减。\\
结果复现如下所示：

\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_47_1.png}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth} 
		\hspace{2mm}
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_47_2.png}
	\end{minipage}
\end{figure}
\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_47_3.png}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth} 
		\hspace{2mm}
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_47_4.png}
	\end{minipage}
\end{figure}
\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_47_5.png}
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth} 
		\hspace{2mm}
		\includegraphics[width=5.5cm,height=3.5cm]{na_exe9_47_6.png}
	\end{minipage}
\end{figure}

\section*{Exe9.51:}
\[
\begin{aligned}
&\because dimR(I_{2h}^{h})=\dfrac{n}{2}-1 \quad \therefore r(I_{2h}^{h})=\dfrac{n}{2}-1\\
&\therefore dimR(I_{h}^{2h})=r(I_{h}^{2h})=r((I_{h}^{2h})^{T})=r(I_{2h}^{h})=\dfrac{n}{2}-1\\
&\because R^{n-1}=R(I_{2h}^{h})\oplus N((I_{2h}^{h})^{T})=R(I_{2h}^{h})\oplus N(I_{h}^{2h})\\
&\therefore dimN(I_{h}^{2h})=n-1-(\dfrac{n}{2}-1)=\dfrac{n}{2}
\end{aligned}
\]

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
